/*
day92
2019.11.28
*/
#include<stdlib.h>
#include<queue>
using namespace std;

struct TreeNode{
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};


class Solution {
public:
    TreeNode* addOneRow(TreeNode* root, int v, int d) {
        if(d==1)
        {
        	TreeNode *cur=new TreeNode(v);
        	cur->left=root;
        	cur->right=NULL; 
        	root=cur;
        	return root;
		}
		
		queue<struct TreeNode *> que;
		que.push(root);
		for(int i=1;i<d-1;i++)
		{
			int time=que.size();
			for(int j=0;j<time;j++)
			{
				struct TreeNode *cur=que.front();
				if(cur->left) 
				{
					que.push(cur->left);
				}
				if(cur->right) 
				{
					que.push(cur->right);
				}
				que.pop();
			}
		}
		
		while(!que.empty()) 
		{
			struct TreeNode *lef=new TreeNode(v);
			struct TreeNode *rig=new TreeNode(v);
			
			
			struct TreeNode *cur=que.front();
			que.pop();
			
			lef->left=cur->left;
			lef->right=NULL;
			
			rig->right=cur->right;
			rig->left=NULL;
			
			cur->left=lef;
			cur->right=rig;
		}
		return root;
    }
};
int main()
{
	return 0;
}
